#ifndef __LINKED_LIST__
#define __LINKED_LIST__

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/*
 * 有表头的单向链表
 */

// 类型接口
struct Node;
typedef struct Node Node;
typedef Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position; // Node*

typedef int ElementType;
struct Node
{
    ElementType data;
    PtrToNode next;
};

// 函数接口
// ctor 和 dtor
void Init(List *l);    // 初始化
void Destroy(List *l); // 析构
// 判空
int IsEmpty(List l);
// 判尾
int IsLast(List l, Position p); // 检查地址 p 是否是链表末尾
// 头尾迭代器
Position First(List l);
Position Last(List l); // 返回尾节点地址，不是 NULL
// 头尾元素
ElementType FirstValue(List l);
ElementType LastValue(List l);
// 删
void push_front(List l, ElementType e);     // 头删
int Delete_by_value(List l, ElementType e); // 删除首个特定值为 e 的元素
void Delete_by_pos(List l, Position p);     // 删除特定位置的元素，注意 p 是指针
void MakeEmpty(List l);                     // 清空链表，保留表头
// 增
ElementType pop_front(List l); // 头插
/**
 * 在位置 p 后插入元素
 * example：
 * Insert(lst, Find(lst,e1), e2)
 * Insert(lst, FindPrevious(lst,e1), e2)
 */
void Insert(List l, Position p, ElementType e);
// 查
Position Find(List l, ElementType e);         // 找到返回地址，找不到返回 NULL
Position FindPrevious(List l, ElementType e); // 找到返回前一个元素的地址，找不到返回 NULL
// 改
void Modify(List l, Position p, ElementType new);
// 其他
int Iscontained(List l, ElementType e); // 检查 e 是否在链表内。在返回真，不在返回假
void sort(List l);                      // 排序
void Display(List l);                   // 展示链表元素（应该由用户完成）
void Reverse(List l);                   // 逆序

#endif /* LinkedList.h */
